package leetcode.median;

import java.util.Deque;
import java.util.LinkedList;

public class $934_ShortestBridge {

    int row;

    int col;

    Deque<int[]> deque;

    int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int shortestBridge(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        deque = new LinkedList<>();
        boolean flag = false;
        for (int i = 0; i < row; i++) {
            if (flag) {
                break;
            }
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j);
                    flag = true;
                    break;
                }
            }
        }
        int step = 0;
        while (!deque.isEmpty()) {
            step++;
            int size = deque.size();
            for (int i = 0;i < size; i++) {
                int[] pair = deque.pollFirst();
                int x = pair[0];
                int y = pair[1];
                for (int k = 0;k < 4;k++) {
                    int curX = x + direction[k][0];
                    int curY = y + direction[k][1];
                    if (isArea(curX, curY)) {
                        if (grid[curX][curY] == 2) {
                            continue;
                        }
                        if (grid[curX][curY] == 1) {
                            return step;
                        }
                        grid[curX][curY] = 2;
                        deque.offerLast(new int[]{curX, curY});
                    }
                }
            }
        }
        return 0;
    }

    public void dfs(int[][] grid, int i, int j) {
        if (!isArea(i, j) || grid[i][j] == 2) {
            return;
        }
        if (grid[i][j] == 0) {
            deque.offerLast(new int[]{i, j});
            return;
        }
        grid[i][j] = 2;
        for (int k = 0; k < 4;k++) {
            int curX = i + direction[k][0];
            int curY = j + direction[k][1];
            dfs(grid, curX, curY);
        }
    }

    public boolean isArea(int i, int j) {
        return i >= 0 && i < row && j >= 0 && j < col;
    }
}
